package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-29 23:17
 **/
public class LeetCode786 {

    //优先队列
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> arr[x[0]] * arr[y[1]] - arr[x[1]] * arr[y[0]]);
        int len = arr.length;
        //录入len-1个最小的素数分数
        for (int i = 1; i < len; i++) {
            queue.offer(new int[]{0, i});
        }
        //移除k-1个最小的素数分数
        for (int i = 1; i < k; i++) {
            int[] poll = queue.poll();
            int a = poll[0];
            int b = poll[1];

            if (a + 1 < b) {
                queue.offer(new int[]{a + 1, b});
            }
        }
        return new int[]{arr[queue.peek()[0]], arr[queue.peek()[1]]};
    }

    //自定义排序
    /*public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        List<int[]> list = new ArrayList<>();
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                list.add(new int[]{arr[i], arr[j]});
            }
        }

        Collections.sort(list, (x, y) -> x[0] * y[1] - x[1] * y[0]);
        return list.get(k - 1);
    }*/

}
